package _2022.hot100._236_二叉树的最近公共祖先;

/**
 * @author： YHSimon
 * @date： 2022-05-18 08:33
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

    TreeNode(int x, TreeNode left,TreeNode right){
        this.val=x;
        this.left=left;
        this.right=right;
    }
}

public class Solution {
    // 6ms
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null && right == null) return null; // 1.
        if(left == null) return right; // 3.
        if(right == null) return left; // 4.
        return root; // 2. if(left != null and right != null)
    }

    // 合并
    public TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q){
        if (root==null||root==p||root==q) return root;
        TreeNode left=lowestCommonAncestor2(root.left, p, q);
        TreeNode right=lowestCommonAncestor2(root.right, p, q);
        if(left==null) return right;
        if(right==null) return left;
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
